#include<cstdio>//uncle-lu
#include<cstring>
#include<queue>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

void add_edge(int, int);
void spfa_1(void);
void spfa_2(void);

struct node{
	int v,next;
};
node edge[1000010];
int head[100010], cnt;
node edge_2[1000010];
int head_2[100010], cnt_2;
int line[100010];
bool visit[100010];
int d_1[100010], d_2[100010];
int n, m;

void add_edge(int x, int y)
{
	edge[++cnt].next=head[x];
	edge[cnt].v = y;
	head[x] = cnt;
	return ;
}

void add_edge_2(int x, int y)
{
	edge_2[++cnt_2].next=head_2[x];
	edge_2[cnt_2].v = y;
	head_2[x] = cnt_2;
	return ;
}


void spfa_1()
{
	memset(visit,false,sizeof(visit));
	memset(d_1,0x7f7f7f7f,sizeof(d_1));

	std::queue<int>qu;
	visit[1] = true;
	qu.push(1);
	d_1[1] = line[1];
	while(!qu.empty())
	{
		int now = qu.front();
		qu.pop();
		visit[now] = false;
		for(int i=head[now];~i;i=edge[i].next)
			if(d_1[edge[i].v] > std::min(d_1[now], line[edge[i].v]) )
			{
				d_1[edge[i].v] = std::min(d_1[now], line[edge[i].v]);
				if(!visit[edge[i].v])
				{
					visit[edge[i].v] = true;
					qu.push(edge[i].v);
				}
			}
	}

	return ;
}

void spfa_2()
{
	memset(visit,false,sizeof(visit));
	memset(d_2,-0x7f7f7f7f,sizeof(d_2));

	std::queue<int>qu;
	visit[n] = true;
	qu.push(n);
	d_2[n] = line[n];
	while(!qu.empty())
	{
		int now = qu.front();
		qu.pop();
		visit[now] = false;
		for(int i=head_2[now];~i;i=edge_2[i].next)
			if(d_2[edge_2[i].v] < std::max(d_2[now], line[edge_2[i].v]))
			{
				d_2[edge_2[i].v] = std::max(d_2[now], line[edge_2[i].v]);
				if(!visit[edge_2[i].v])
				{
					visit[edge_2[i].v] = true;
					qu.push(edge_2[i].v);
				}
			}
	}

	return ;

}

int main()
{
	memset(head,-1,sizeof(head));
	memset(head_2,-1,sizeof(head));

	int x, y, model;
	read(n);read(m);
	for(int i=1;i<=n;++i)
		read(line[i]);

	for(int i=1;i<=m;++i)
	{
		read(x); read(y); read(model);
		add_edge(x,y);
		add_edge_2(y,x);
		if(model == 2)
		{
			add_edge(y,x);
			add_edge_2(x,y);
		}
	}
	
	spfa_1();
	spfa_2();

	int ans = 0;
	for(int i=1;i<=n;++i)
		ans = std::max(ans, d_2[i] - d_1[i]);

	printf("%d", ans);

	return 0;
}
